package org.example.l0;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class dp {

    public int minDistance(String word1,
                           String word2) {
        int len1 = word1.length(), len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        IntStream.rangeClosed(0, len1).forEach(n -> dp[n][0] = n);
        IntStream.rangeClosed(0, len2).forEach(n -> dp[0][n] = n);

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                char a = word1.charAt(i - 1), b = word2.charAt(j - 1);
                if (a == b) {
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }

                int v1 = dp[i - 1][j], v2 = dp[i][j - 1], v3 = dp[i - 1][j - 1];
                int min = IntStream.of(v1, v2, v3).min().getAsInt();
                dp[i][j] = min + 1;
            }
        }

        return dp[len1][len2];
    }

    public int longestCommonSubsequence(String text1,
                                        String text2) {
        int len1 = text1.length(), len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                char a = text1.charAt(i - 1), b = text2.charAt(j - 1);
                if (a == b) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    continue;
                }

                int v1 = dp[i - 1][j], v2 = dp[i][j - 1], v3 = dp[i - 1][j - 1];
                dp[i][j] = IntStream.of(v1, v2, v3).max().getAsInt();
            }
        }
        return dp[len1][len2];

    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        int[] dp = new int[numRows];
        Arrays.fill(dp, 1);

        for (int i = 0; i < numRows; i++) {
            int former = 1, cur;
            for (int j = 1; j <= i - 1; j++) {
                cur = dp[j];
                dp[j] = former + cur;
                former = cur;
            }

            List<Integer> collect = Arrays.stream(dp).limit(i + 1).mapToObj(Integer::valueOf).collect(Collectors.toList());
            res.add(collect);
        }

        return res;
    }

    public int coinChange(int[] coins,
                          int amount) {
        if (amount <= 0) {
            return -1;
        }

        int len = coins.length;
        if (len == 0) {
            return -1;
        }

        int[][] dp = new int[len + 1][amount + 1];
        Arrays.fill(dp[0], amount + 1);
        dp[0][0] = 0;

        for (int i = 1; i <= len; i++) {
            int coin = coins[i - 1];
            for (int j = 1; j <= amount; j++) {
                if (coin > j) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coin] + 1);
            }
        }

        return dp[len][amount];
    }

    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        int maxLen = 0;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        for (int i = 1; i < len; i++) {
            int a = nums[i];
            for (int j = 0; j < i; j++) {
                if (nums[j] < a) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len <= 2) {
            return false;
        }

        int sum = Arrays.stream(nums).sum(), max = Arrays.stream(nums).max().getAsInt();
        if ((sum % 2 == 1)) {
            return false;
        }

        int target = sum >> 1;
        if (max > target) {
            return false;
        }

        boolean[][] dp = new boolean[len][target + 1];
        for (int i = 0; i < len; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < len; i++) {
            int v = nums[i];
            for (int j = 1; j <= target; j++) {
                if (v > j) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                dp[i][j] = dp[i - 1][j] | dp[i - 1][j - v];
            }
        }

        return dp[len - 1][target];
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int ans = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                ans = Math.min(dp[i - j * j], ans);
            }

            dp[i] = ans + 1;
        }

        return dp[n];
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= i; j++) {
                String substring = s.substring(j, i);
                if (dp[j] && set.contains(substring)) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[len];
    }
}

